package leetcode_周赛._2023._09;

import java.util.List;

/**
 * 第 364 场周赛 <p>
 * AC_2
 *
 * @author yezh
 * @date 2023/9/25 9:04
 */
public class _24 {

    /**
     * 2866.美丽塔 II <p />
     * 算法：前缀和 + 单调栈 <p />
     * 要点：如果把当前位置作为山脉, 只需要知道左边递增元素的和和右边递减元素的和即可
     * 从右往左递增: 7 2(7 要变成 2, 对于 9 作为峰顶时) 9 3 (对于 5 作为峰顶时, 9 要变成 3) 5 6 <p />
     * 从左往右递增: 6 5(6 要变成 5) 3(6, 5 要变成 3) 9 2(6, 5, 3, 9 要变成 2) 7 <p />
     * 当前数会影响前几个数, 例如: 1 2 3 4 2, 到最后一个 2 时, 需要将 2、3、4 都改成 2 <p />
     * pre[i]: nums[0 ... i] 递增时的所有元素和 <p />
     * 所以, 需要找到左边第一个小于当前第 i 个元素的位置 j, 将 [j, i] 的元素值改为 maxHeights[i] <p />
     * 6,5,3,9,2,7
     * 从左往右递增, 6 -> 5(将 6 变成 5) -> 3(将 6, 5 变成 3) -> 9 -> 2(将 6, 5, 3, 9 变成 2) -> 7
     * 到第 i 个元素时, [0, i - 1] 的元素是递增的
     */
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size(), top = -1;
        long[] pre = new long[n + 1];
        // 使用单调栈找到左边（或右边）第一个小于 maxHeights[i] 的数
        int[] st = new int[n + 1];
        st[++top] = -1;
        for (int i = 0; i < n; i++) {
            int x = maxHeights.get(i);
            while (top > 0 && x <= maxHeights.get(st[top])) {
                int j = st[top--];
                // 从 st[top] 到 j 都是 maxHeights[j]
                pre[i] -= (long) maxHeights.get(j) * (j - st[top]);
            }
            // 从 st[top] 到 i 都是 x
            pre[i + 1] = pre[i] + (long) x * (i - st[top]);
            st[++top] = i;
        }
        top = -1;
        st[++top] = n;
        long ans = 0, suf = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = maxHeights.get(i);
            long preSuf = suf;
            while (top > 0 && x <= maxHeights.get(st[top])) {
                int j = st[top--];
                // 从 j 到 st[top] 都是 maxHeights[j]
                suf -= (long) maxHeights.get(j) * (st[top] - j);
            }
            suf += (long) x * (st[top] - i);
            st[++top] = i;
            ans = Math.max(ans, x + pre[i] + preSuf);
        }
        return ans;
    }

}
